
\subsection{Catalan 数列}

以下问题属于 Catalan 数列:

\begin{enumerate}
\item 有 $2n$ 个人排成一行进入剧场。入场费 5 元。其中只有$n$个人有一张 5 元钞票，另外 $n$ 人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
\item 一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处工作。每天她走 $2n$ 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
\item 在圆上选择 $2n$ 个点, 将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数？
\item 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
\item 一个栈 (无穷大) 的进栈序列为 $1,2,3, \cdots ,n$ 有多少个不同的出栈序列？
\item $n$ 个结点可够造多少个不同的二叉树？
\item $n$ 个不同的数依次进栈，求不同的出栈结果的种数？
\item $n$ 个 $+1$ 和 $n$ 个 $-1$ 构成 $2n$ 项 $a_1,a_2, \cdots ,a_{2n}$，其部分和满足 $a_1+a_2+ \cdots +a_k>=0(k=1,2,3, \cdots ,2n)$ 对与 $n$ 该数列为？
\end{enumerate}

其对应的序列为:

\begin{tabular}{cccccccc}
\hline
H\_0& H\_1& H\_2& H\_3& H\_4& H\_5& H\_6& ...\\1& 1& 2& 5& 14& 42& 132& ...\\\hline
\end{tabular}

(Catalan 数列）

该递推关系的解为:

$$
H_n=\frac{C_{2n}^{n}}{n+1}(n=1,2,3,\cdots)
$$
